#include<bits/stdc++.h>
#define int long long
#define N 10000005
using namespace std;
int n,mod;
int fac[N],inv[N],h[N];
int p[N];
int f[3005][3005];
int ans;
inline int Pow(int x,int y){
    x%=mod;
    int z=1;
    while(y){
        if(y&1) z=z*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return z;
}
inline int C(int n,int m){
    if(n<m||n<0||m<0) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline void init(){
    fac[0]=inv[0]=h[0]=1;
    for(int i=1;i<=n;i++) h[i]=h[i-1]*2%mod;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    inv[n]=Pow(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
    p[0]=p[1]=1;
    for(int i=2;i<=n;i++) p[i]=Pow(i,i-1);
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=1;k<=j;k++){
                f[i][j]=(f[i][j]+f[i-1][j-k]*p[k]%mod*C(n-(j-k),k)%mod)%mod;
            }
        }
    }
}
signed main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%lld %lld",&n,&mod);
    init();
    for(int i=1;i<=n;i++){
        ans=(ans+h[n-i]%mod*f[i][n]%mod)%mod;
    }
    printf("%lld",ans);
    return 0;
}